from typing import List


class Solution:
    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:
        n, m = len(box), len(box[0])

        ans = [["."] * n for _ in range(m)]

        # 转移所有障碍物的位置
        for i2 in range(m):
            for j2 in range(n):
                i1, j1 = n - j2 - 1, i2
                # print((i1, j1), "->", (i2, j2))
                if box[i1][j1] == "*":
                    ans[i2][j2] = "*"

        # 转移所有障碍物上石头的数量
        for j2 in range(n):
            num = 0
            for i2 in range(m):
                i1, j1 = n - j2 - 1, i2
                # print((i1, j1), "->", (i2, j2))
                if box[i1][j1] == "#":
                    num += 1
                elif box[i1][j1] == "*":
                    for i3 in range(i2 - 1, i2 - 1 - num, -1):
                        ans[i3][j2] = "#"
                    num = 0
            for i3 in range(m - 1, m - 1 - num, -1):
                ans[i3][j2] = "#"

        return ans


if __name__ == "__main__":
    # [["."],
    #  ["#"],
    #  ["#"]]
    print(Solution().rotateTheBox(box=[["#", ".", "#"]]))

    # [["#","."],
    #  ["#","#"],
    #  ["*","*"],
    #  [".","."]]
    print(Solution().rotateTheBox(box=[["#", ".", "*", "."],
                                       ["#", "#", "*", "."]]))

    # [[".","#","#"],
    #  [".","#","#"],
    #  ["#","#","*"],
    #  ["#","*","."],
    #  ["#",".","*"],
    #  ["#",".","."]]
    print(Solution().rotateTheBox(box=[["#", "#", "*", ".", "*", "."],
                                       ["#", "#", "#", "*", ".", "."],
                                       ["#", "#", "#", ".", "#", "."]]))
